package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

import java.util.*;

/**
 * @author lixiaowen
 * @create 2020-01-03
 */
public class UniqueBinarySearchTreesII95 {

    static class Solution {
        private Set<String> exist = new HashSet<>();

        public List<TreeNode> generateTrees(int n) {
            List<TreeNode> result = new ArrayList<>();
            generateTree(n, new boolean[n], 0, result, null);
            return result;
        }

        public static String preOrder(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if (root == null) return "";
            Stack<TreeNode> stack = new Stack<>();
            TreeNode node = root;
            stack.push(node);
            while (!stack.isEmpty()) {
                node = stack.pop();
                list.add(node.val);
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
            StringBuilder sb = new StringBuilder();
            for (Integer integer : list) {
                sb.append(integer + "-");
            }
            return sb.toString();
        }

        private void generateTree(final int n, final boolean[] used, final int treeSize,
                                  final List<TreeNode> result, final TreeNode root) {
            if (treeSize >= n && n > 0) {
                String preOrder = preOrder(root);
                if (!exist.contains(preOrder)) {
                    result.add(root);
                    exist.add(preOrder);
                }
                return;
            }
            for (int i = 1; i <= n; i++) {
                if (used[i - 1]) continue;
                used[i - 1] = true;
                TreeNode newTreeRoot = insertNode(root, i);
                generateTree(n, used, treeSize + 1, result, newTreeRoot);
                //还原状态
                used[i - 1] = false;
                //因为每次插入结点均是新建一棵树,即没有改动root树,所以不用"还原 新增"结点
            }
        }

        private TreeNode copyTree(final TreeNode oldRoot) {
            TreeNode root = new TreeNode(oldRoot.val);
            //采用先根遍历
            if (oldRoot.left != null) {
                root.left = copyTree(oldRoot.left);
            }

            if (oldRoot.right != null) {
                root.right = copyTree(oldRoot.right);
            }
            return root;
        }

        private TreeNode insertNode(final TreeNode oldRoot, final int val) {
            TreeNode node = new TreeNode(val);
            if (oldRoot == null) return node;
            TreeNode root = copyTree(oldRoot);
            TreeNode parent = root;
            while (parent != null) {
                TreeNode tn = val < parent.val ? parent.left : parent.right;
                if (tn == null) {
                    if (val < parent.val) {
                        parent.left = node;
                    } else {
                        parent.right = node;
                    }
                }
                parent = tn;
            }
            return root;
        }

    }

    /**
     * 递归
     * 123   4 5
     */
    static class Solution2 {

        public List<TreeNode> generateTrees(int n) {
            if (n == 0) return new ArrayList<>();
            return generate(1, n);
        }

        private List<TreeNode> generate(int left, int right) {
            if (left >= right) {
                TreeNode node = left == right ? new TreeNode(left) : null;
                return new ArrayList<TreeNode>() {{
                    add(node);
                }};
            }
            List<TreeNode> result = new ArrayList<>();
            for (int i = left; i <= right; i++) {
                List<TreeNode> leftTrees = generate(left, i - 1);
                List<TreeNode> rightTrees = generate(i + 1, right);
                for (int j = 0; j < leftTrees.size(); j++) {
                    for (int k = 0; k < rightTrees.size(); k++) {
                        TreeNode root = new TreeNode(i);
                        root.left = copyTree(leftTrees.get(j));
                        root.right = copyTree(rightTrees.get(k));
                        result.add(root);
                    }
                }
            }
            return result;
        }


        private TreeNode copyTree(TreeNode node) {
            if (node == null) return null;
            TreeNode root = new TreeNode(node.val);
            if (node.left != null) root.left = copyTree(node.left);
            if (node.right != null) root.right = copyTree(node.right);
            return root;
        }

    }

    public static void main(String[] args) {
//        Solution solution = new Solution();
        Solution2 solution = new Solution2();
        int start = 3;
        for (int i = start; i < start + 1; i++) {
            List<TreeNode> nodes = solution.generateTrees(i);
            System.out.println(i + "\t" + nodes.size());
            nodes.stream().forEach(node -> System.out.println(TreeNode.preOrder(node)));
        }
    }
}
